/**
 * 桶排序：
 * 1、预先申请一段空间，循环原数组，在新数组对应位置设置一个不为空的值占位
 * 2、循环新数组，清空原数组，此时新数组中存在许多空值，通过for in循环，过滤掉空值，剩下的数据依次放到原数组内即完成排序
 * 特点：消耗空间，所需空间是数组中最大数字+1
 * 时间复杂度：
 * @param {Array} array 
 * @returns Array
 */
function tongSort(array) {
  let bucket = [];
  for (let i = 0; i < array.length; i++) {
    const element = array[i];
    // 相同数组在同一位置多次出现
    if(bucket[element]) {
      bucket[element]++;
    } else {
      bucket[element] = 1;
    }
  }
  array = [];
  for(let item in bucket) {
    let times = bucket[item];
    for(let i=0;i<times;i++) {
      array.push(item*1);
    }
  }
  console.log(bucket.length)
  return array;
}

console.log(tongSort([8,100,50,22,15,6, 0,1,1000,999,0]));